/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-04-26
 * Time:20:18
 */

/**
 * BM20数组中的逆序对
 */

public class InversePairs {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 0};
        System.out.println(InversePairs(nums));
        for (int i = 0; i < nums.length;i++) {
            System.out.println(nums[i]);
        }
    }
    private static final int MOD = 1000000007;
    public static int InversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] tmp = new int[nums.length];

        return mergeSort(nums, tmp, 0, nums.length - 1);
    }

    private static int mergeSort(int[] nums, int[] tmp, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, tmp, left, mid) % MOD + mergeSort(nums, tmp,
                mid + 1, right) % MOD;
        int i = mid, j = right, k = right;
        while (i >= left && j >= mid + 1) {
            if (nums[i] > nums[j]) {
                tmp[k--] = nums[i--];
                count = (count + j - mid) % MOD;
            } else {
                tmp[k--] = nums[j--];
            }
        }
        while (i >= left) {
            tmp[k--] = nums[i--];
        }
        while (j >= mid + 1) {
            tmp[k--] = nums[j--];
        }
        for (k = left; k <= right; k++) {
            nums[k] = tmp[k];
        }
        return count % MOD;
    }
}
